#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//插入操作
#define AFTER_OBJ	1
#define BEFORE_OBJ	2

//添加到
#define HEAD_POS	0
#define TAIL_POS	1

struct node{
	int val;
	struct node *next;
};

typedef struct list {
	int size;
	struct node *head;
	struct node *tail;
} list_t;
list_t *g_list = NULL;

void list_init(list_t **list)
{
	(*list) = malloc(sizeof(list_t));
	(*list)->size = 0;
	(*list)->head = NULL;
	(*list)->tail = NULL;
}



//在xx位置添加节点，链表头或尾
int add_node_to_xx(int value, int flag)
{
	if (flag != HEAD_POS && flag != TAIL_POS) return -1;//操作传参错误
	
	struct node *newnode = malloc(sizeof(*newnode));
	if (newnode == NULL) return -2;
	
	newnode->val = value;
	newnode->next = NULL;
	if (g_list->size == 0) {
		g_list->head = newnode;
		g_list->tail = newnode;
	} else {
		if (flag == HEAD_POS) {
			newnode->next = g_list->head;
			g_list->head = newnode;
		} else {
			g_list->tail->next = newnode;
			g_list->tail = newnode;
		}
	}
	g_list->size++;
	return 0;
}

// 创建一个节点，并插入到obj之后
int add_node_afterobj(struct node *obj, int value)
{
	struct node *newnode = malloc(sizeof(*newnode));
	assert(newnode);

	newnode->val = value;
	newnode->next = obj->next;
	obj->next = newnode;
	g_list->size++;
	return 0;
}

//打印链表
void print_list() 
{
	struct node *head = g_list->head;
	printf("list size: %d\n",g_list->size);
	while (head) {
		printf("%d", head->val);
		head = head->next;
		if (head) printf("->");
	}
	printf("\r\n");
}
// 找到value节点的直接前驱，注意没考虑首尾情况
struct node *find_prev_node(int value)
{
	struct node *prev, *cur = g_list->head;
	prev = cur;
	while (cur && cur->val != value) {
		prev = cur;
		cur = cur->next;
	}
	return (cur != NULL)? prev:NULL;	//是否找到节点前驱
}

struct node *find_node(int value)
{
	struct node *cur = g_list->head;
	while (cur && cur->val != value) {
		cur = cur->next;
	}
	return (cur != NULL)? cur:NULL;
}

// 在目标节点之前还是之后插入
int insert_obj_xx(int obj, int value, int flag) 
{
	if (flag != BEFORE_OBJ && flag != AFTER_OBJ) return -1; //操作传参错误
	
	if (g_list->size == 0 || g_list->head->val == obj)
		add_node_to_xx(value, HEAD_POS);
	else if (g_list->tail->val == obj)
		add_node_to_xx(value, TAIL_POS);
	else {
		struct node *temp;
		if (flag == BEFORE_OBJ)
			temp = find_prev_node(obj);
		else
			temp = find_node(obj);

		if (temp == NULL) {		
			printf("cann't find obj_node\n");
			return -1;	
		} else {
			add_node_afterobj(temp,value);
		}
	}
	return 0;
}

// 在第n个位置（前面）插入，即插入后节点的位置为n
int insert_pos(int pos, int value)
{
	// pos位置要合法
	assert (pos <= g_list->size);

	if (g_list->size == 0 || pos == 1) {
		add_node_to_xx(value, HEAD_POS);
	} else if (pos == g_list->size) {
		add_node_to_xx(value, TAIL_POS);
	} else {
		// 找到前一个节点 	
		struct node *head = g_list->head;
		for (int i = 1; i < pos-1; i++) {
			head = head->next;
		}
		add_node_afterobj(head, value);
	}
	return 0;
}

int delete(int value)
{
	assert(g_list->size >= 0);

	struct node *prev, *cur = g_list->head;
	prev = cur;
	while (cur && cur->val != value) {
		prev = cur;
		cur = cur->next;
	}
	if (cur != NULL) {	// 找到对应节点 
		if (prev == cur)	{ //如果cur没有移动，删除目标为头节点
			g_list->head = prev->next;
			free(prev);
		} else {
			prev->next = cur->next;
			free(cur);
		}
		g_list->size--;
	} else {
		printf("cann't find obj.\n");
		return -1;
	}
	return 0;
}
int insert_mid(int value)
{
	struct node *slow, *fast;
	struct node *dummy = malloc(sizeof(*dummy));
	dummy->next = g_list->head;
	slow = fast = dummy;
	while (fast != NULL && fast->next != NULL) {
		slow = slow->next;
		fast = fast->next->next;
	}
	//中间为slow->next
	dummy->val = value;
	dummy->next = slow->next;
	slow->next = dummy;
	g_list->size++;
	return 0;
}
int main()
{
	int i, arr[5] = {9, 12, -1, 3, 27};
	list_init(&g_list);
	for (i = 0; i < 5; i++)
		add_node_to_xx(arr[i], HEAD_POS);
	print_list();
	insert_obj_xx(-1, 33, BEFORE_OBJ);
	insert_obj_xx(9,101, AFTER_OBJ);
	// insert_obj_prev(9,88);
	delete(3);
	insert_mid(500);
	// delete(27);
	// delete(101);
	print_list();
	return 0;
}
